In a memory system including a flash memory, when a unit of data erasing (block) and a unit of data read and write are different, according to the progress of rewriting of the flash memory , the blocks are made porous by invalid data (not the latest) data. When the blocks in such a porous state increases, usable blocks decrease and a storage area of the flash memory cannot be effectively used. Therefore, compaction is executed by collecting valid data in a compaction source block and moving the collected data to a compaction destination block, thereby increasing the number of unused blocks.
In the compaction process, it is required to determine whether the data in the compaction source block is valid or invalid. Therefore, a reverse-lookup address translation table (Reverse Lookup Table) is prepared for performing translation from a physical address in the flash memory to a logical address specified by a host. Meanwhile, translation from the logical address to the physical address is performed by using a lookup address translation table (Lookup Table).